package com.mamingchao.basic.heap;

import com.mamingchao.basic.arraysort.Sortable;

/**
 * Created by mamingchao on 2024/5/3.
 * 给定一个数组，生成大根堆
 * 此方法为自己写，就是 左老师说的heapInsert
 */
public class MaxRootValueHeap implements Sortable {

    public static void main(String[] args) {
        final int[] regularHeap = new int[] {3, 2, 4, 5, 7, 8 , 9 };
        MaxRootValueHeap mxh = new MaxRootValueHeap();
        mxh.genereteMaxRootValueHeap(regularHeap);
    }



    public void genereteMaxRootValueHeap(int[] regularHeap){
        if (regularHeap == null || regularHeap.length == 0)
            throw new RuntimeException("输入的常规堆错误");

        // i==0 的位置越过，因为当只有0一个元素的时候，默认就是 最大根
        // 从上往下，一个node 一个node的遍历判断，自己是不是比自己的父亲大；如果大一路往上
        //O(N)
        for (int i = 1; i < regularHeap.length; i++) {

            int myIndex = i;

            this.nodeDealer(regularHeap, myIndex);
        }

        printArray(regularHeap);
    }

    /**
     * 将 根到 myIndex 的一条路径上的所有元素做对比处理，让value最大的元素，上浮到root上
     * 这个 dealer 只适合数组从前到后，堆结构从上到下遍历的方式
     * @param regularHeap
     * @param myIndex
     */
    private void nodeDealer(int[] regularHeap, int myIndex){

        //O(logN)
        while (myIndex > 0) {
            int myRootIndex = this.getParentNodeIndex(myIndex);

            if (regularHeap[myIndex] > regularHeap[myRootIndex])
                swap(regularHeap, myIndex, myRootIndex);

            myIndex = myRootIndex;
        }
    }

    // 此方法等同于上面的nodeDealer； 上面的nodeDealer是自己写的，下面的heapInsert 是老师教的
    private void heapInsert(int[] regularHeap, int myIndex) {
        // 父亲节点的index 是如下的值
        // int myRootIndex = (myIndex -1)/2;
        while (regularHeap[myIndex] > regularHeap[(myIndex -1)/2]) {
            swap(regularHeap, myIndex, (myIndex -1)/2);
            myIndex = (myIndex -1)/2;
        }
    }


    /**
     * 与大根堆对应的数组的索引，从0开始的情况，获取父索引的方法
     * @param childIndex
     * @return
     */
    int getParentNodeIndex(int childIndex) {
        if (childIndex < 0)
            throw new RuntimeException("错误的子节点索引值");

        if (childIndex == 0)
            return 0;

        return (childIndex-1)/2;
    }

    @Override
    public void sort(int[] arr, int start, int end) {

    }
}
